//
// Created by liushuai on 2021/1/27.
//

#include "mergeKLists.h"
ListNode *mergeList(ListNode *head1, ListNode *head2) {
  if (head1 && !head2)
    return head1;
  else if (!head1 && head2)
    return head2;
  else if (!head1 && !head2)
    return head1;
  else {
    if (head1->val < head2->val) {
      head1->next = mergeList(head1->next, head2);
      return head1;
    } else {
      head2->next = mergeList(head1, head2->next);
      return head2;
    }
  }
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
  if (lists.empty())
    return nullptr;
  else if (lists.size() == 1)
    return lists[0];
  else {
    ListNode *res = nullptr;
    do {
      res = mergeList(lists[0], lists[1]);
      lists.erase(lists.begin(), lists.begin() + 2);
      lists.push_back(res);
    } while (lists.size() != 1);
    return lists[0];
  }
}